package org.example.myleet.slidewindow;

import org.example.myleet.Utils.Assert;

import java.util.*;

public class SlideWindowSolution {
    //p3
    /**
     * substring window with two index
     * 双游标窗口滑动法
     * 1、右游标往右边移动
     * 2、如果右游标位置的字符在子串中曾经出现过，则此子串成为候选子串，计算一次最长子串长度，
     * 然后左游标右移，弹出字符，直到左游标找到曾经出现过的字符，并跳过（这个字符现在在子串右
     * 游标中）
     * 3、在字符串中滑窗完成后，计算最后的子串长度检验是否刷新最长
     *
     * 最坏情况下复杂度应该是O(2n)
     * 3 ms
     */
    public int lengthOfLongestSubstring(String s) {
        if (1 > s.length()) {
            return 0;
        }
        int left = 0, right = 0, max = 0;
        //记录字符出现的位置，类似于map的作用
        int[] charPosition = new int[128];
        while (right < s.length()) {
            char c = s.charAt(right);
            if (charPosition[c] == 0) {
                //字符没出现过，标记一下并往右边滑
                charPosition[c] = 1;
            } else {
                //字符在子串中出现过
                //先刷新一次子串长度记录
                max = Math.max(max, right - left);
                char d = s.charAt(left);
                while (c != d && left < right) {
                    //左游标往右边移动，只要还没找到这个重复出现的字符就一直移动并弹出曾经出现的字符
                    charPosition[d] = 0;
                    ++left;
                    d = s.charAt(left);
                }
                //到达重复出现的字符位置，跳过此字符
                ++left;
            }
            ++right;
        }
        //最后补充计算最后一个未经过检查的子串长度，试探刷新记录
        max = Math.max(max, right - left);
        return max;
    }

    //p28
    /**
     * 0 ms
     * 滑动窗口，对首尾符合的窗口内子串再完全检查一次，最差的时间复杂度为O(mn)，运气好的时候O(n)（就是整个needle的首尾字符在haystack中出现的频率低），今天的测试用例太巧，让复杂度接近O(n)
     */
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        if (m < n) {
            return -1;
        }
        if (n == 0) {
            return 0;
        }
        char head = needle.charAt(0), tail = needle.charAt(n - 1);
        int headIdx = 0, tailIdx = n - 1;
        while (tailIdx < m) {
            if (head == haystack.charAt(headIdx) && tail == haystack.charAt(tailIdx)) {
                boolean found = true;
                for (int i = 1; i < n - 1; ++i) {
                    if (haystack.charAt(headIdx + i) != needle.charAt(i)) {
                        found = false;
                        break;
                    }
                }
                if (found) {
                    return headIdx;
                }
            }
            ++headIdx;
            ++tailIdx;
        }
        return -1;
    }

    /**
     * 220【滑动窗口+有序Map】存在重复元素 III
     * 62 ms
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int len = nums.length;
        TreeSet<Long> orderedSet = new TreeSet<>();
        for (int i = 0; i < len; ++i) {
            if (orderedSet.contains((long) nums[i])) {
                return true;
            }
            //找到num[i]的比nums[i] - t大的数，如果其小于nums[i] + t，即找到差值绝对值在范围k里面
            Long ceiling = orderedSet.ceiling((long) nums[i] - t);
            if (null != ceiling && ceiling <= (long) nums[i] + t) {
                return true;
            }
            //下面是滑动窗口常规做法
            orderedSet.add((long) nums[i]);
            if (i >= k) {
                orderedSet.remove((long) nums[i - k]);
            }
        }
        return false;
    }

    //p1234
    public int balancedString(String s) {
        int n = s.length() / 4;
        int[] counts = new int[256];
        char[] charArr = s.toCharArray();
        for (int i = 0; i < s.length(); ++i) {
            ++counts[charArr[i]];
        }
        if (counts['Q'] == n && counts['W'] == n && counts['E'] == n) {
            return 0;
        }
        int l = 0, r = 0, min = Integer.MAX_VALUE;
        while (r < s.length()) {
            --counts[charArr[r]];
            ++r;
            while (counts['Q'] <= n && counts['W'] <= n && counts['E'] <= n && counts['R'] <= n) {
                min = Math.min(min, r - l);
                ++counts[charArr[l]];
                ++l;
            }
        }
        return min;
    }

    //p1838
    /**
     * 思路：排序+滑动窗口
     * 题目要求在最多k次元素增大操作后，使得某个元素的频次最高
     * 考虑：
     * 1、先将相同的元素放一起（排序，复杂度O(n*log(n))），这样比较容易知道最多的元素是哪个
     * 2、由于相同的元素堆在一起了，此时考虑加入一个窗口将这些相同元素框在一起，则窗口长度就是元素频次
     * 3、考虑窗口右边界纳入一个新的元素，此时为了让窗口内其他元素变成新的元素，需要消耗增大操作次数
     * 3.1、如果总消耗的增大操作次数在允许的范围内，则成功扩大了窗口的长度
     * 3.2、如果不够消耗，则需要将左边界的元素移除出窗口，并返回对应的操作次数
     * 4、最终在O(n)复杂度下遍历完整个数组就知道窗口最多可以有多长
     */
    public int maxFrequency(int[] nums, int k) {
        //先排序
        Arrays.sort(nums);
        //p：剩余的增大操作次数，l：窗口左边界（包括），r：窗口右边界（包括），maxLen：最大窗口长度，winLen：窗口长度，diff：新的窗口右边界和旧的窗口右边界之间的差值
        int p = k, l = 0, r = 0, winLen = 1, maxLen = winLen, diff;
        while (r < nums.length - 1) {
            //窗口右边界前进
            ++r;
            //计算新的窗口右边界和旧的窗口右边界之间的差值
            diff = nums[r] - nums[r - 1];
            //对窗口内所有元素进行增大操作，使得窗口内元素全部增大到nums[r]
            p -= diff * winLen;
            while (p < 0 && l < r) {
                //如果p小于0，说明增大操作次数不够，需要左边界前进缩小窗口长度以归还操作次数到p中
                p += nums[r] - nums[l];
                //左边界前进
                ++l;
            }
            //求出新的窗口长度
            winLen = r - l + 1;
            maxLen = Math.max(maxLen, winLen);
        }
        return maxLen;
    }

    //p1984
    public int minimumDifference(int[] nums, int k) {
        if (k < 2 || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int minDiff = nums[k - 1] - nums[0];
        for (int i = k; i < nums.length; ++i) {
            minDiff = Math.min(minDiff, nums[i] - nums[i - k + 1]);
        }
        return minDiff;
    }

    //p2024
    public int maxConsecutiveAnswers(String answerKey, int k) {
        char[] charArr = answerKey.toCharArray();
        int maxLen = longestConsensusSeqByReplacement2024(charArr, 'F', k);
        maxLen = Math.max(maxLen, longestConsensusSeqByReplacement2024(charArr, 'T', k));
        return maxLen;
    }
    private int longestConsensusSeqByReplacement2024(char[] charArr, char replacement, int k) {
        int i = 0, l = 0, r = 0, maxLen = 0;
        char c;
        while (i < charArr.length) {
            c = charArr[i];
            if (c == replacement) {
                if (k > 0) {
                    --k;
                } else {
                    while (charArr[l] != replacement) {
                        ++l;
                    }
                    ++l;
                }
            }
            ++r;
            ++i;
            maxLen = Math.max(maxLen, r - l);
        }
        return maxLen;
    }

    //p2379
    public int minimumRecolors(String blocks, int k) {
        int op = 0, l = 0, r = k;
        for (int i = 0; i < k; ++i) {
            char ch = blocks.charAt(i);
            if (ch == 'W') ++op;
        }
        int answer = op;
        while (r < blocks.length()) {
            char ch = blocks.charAt(r);
            if (ch == 'W') ++op;
            ++r;
            ch = blocks.charAt(l);
            if (ch == 'W') --op;
            ++l;
            answer = Math.min(answer, op);
        }
        return answer;
    }

    /**
     * 2537【滑动窗口+哈希表+计数】统计好子数组的数目
     */
    public long countGood(int[] nums, int k) {
        Map<Integer, Integer> numCnt = new HashMap<>();
        long answer = 0L, pairs = 0L;
        int l = 0, r = 0, n = nums.length;
        while (l < n) {
            while (pairs < k && r < n) {
                int num = nums[r];
                int prevCnt = numCnt.getOrDefault(num, 0);
                int currCnt = prevCnt + 1;
                numCnt.put(num, currCnt);
                pairs += (long) currCnt * (currCnt - 1) / 2 - (long) prevCnt * (prevCnt - 1) / 2;
                r++;
            }
            if (pairs < k) break;
            answer += n - r + 1;
            int num = nums[l];
            int prevCnt = numCnt.get(num);
            int currCnt = prevCnt - 1;
            numCnt.put(num, currCnt);
            pairs += (long) currCnt * (currCnt - 1) / 2 - (long) prevCnt * (prevCnt - 1) / 2;
            l++;
        }
        return answer;
    }

    /**
     * 2799【滑动窗口+计数】统计完全子数组的数目
     */
    public int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        int mx = nums[0];
        for (int num : nums) {
            mx = Math.max(mx, num);
        }
        Map<Integer, Integer> missNum = new HashMap<>(mx + 1);
        for (int num : nums) {
            missNum.put(num, 1);
        }
        int answer = 0;
        int[] numCnt = new int[mx + 1];
        int l = 0, r = 0;
        while (l < n) {
            if (r >= n) break;
            numCnt[nums[r]]++;
            missNum.remove(nums[r]);
            r++;
            if (!missNum.isEmpty()) continue;
            while (true) {
                numCnt[nums[l]]--;
                if (numCnt[nums[l]] == 0) {
                    numCnt[nums[l]]++;
                    break;
                }
                l++;
                if (l >= n) break;
            }
            answer += l + 1;
        }
        return answer;
    }

    /**
     * 2831【哈希表+滑动窗口】找出最长等值子数组
     */
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int answer = 1, n = nums.size();
        Map<Integer, List<Integer>> xMapIndices = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int x = nums.get(i);
            List<Integer> indices = xMapIndices.getOrDefault(x, new ArrayList<>());
            indices.add(i);
            xMapIndices.put(x, indices);
        }
        for (List<Integer> indices : xMapIndices.values()) {
            int l = 0, r = 0;
            while (r < indices.size()) {
                int len = r - l;
                if (indices.get(r) - indices.get(l) - len <= k) {
                    ++len;
                    if (answer < len) answer = len;
                    ++r;
                } else {
                    ++l;
                }
            }
        }
        return answer;
    }

    /**
     * 3297【滑动窗口+计数】统计重新排列后包含另一个字符串的子字符串数目 I
     */
    public long validSubstringCount(String word1, String word2) {
        if (word1.length() < word2.length()) return 0L;
        int n = word2.length(), m = word1.length() - n + 1, mismatchCnt = 0;
        int[] w2CharCnt = new int[26];
        for (int i = 0; i < n; ++i) {
            int idx = word2.charAt(i) - 'a';
            if (w2CharCnt[idx] == 0) ++mismatchCnt;
            w2CharCnt[idx]++;
        }
        int l = 0, r = 0;
        int[] charCnt = new int[26];
        while (r - l < n) {
            int idx = word1.charAt(r++) - 'a';
            charCnt[idx]++;
            if (charCnt[idx] == w2CharCnt[idx]) --mismatchCnt;
        }
        long answer = 0L;
        while (l < m) {
            while (r < word1.length() && mismatchCnt > 0) {
                int idx = word1.charAt(r++) - 'a';
                charCnt[idx]++;
                if (charCnt[idx] == w2CharCnt[idx]) --mismatchCnt;
            }
            if (r < word1.length() || mismatchCnt <= 0) {
                answer += word1.length() - r + 1;
            }
            int idx = word1.charAt(l++) - 'a';
            charCnt[idx]--;
            if (charCnt[idx] < w2CharCnt[idx]) ++mismatchCnt;
        }
        return answer;
    }

    /**
     * 3306【滑动窗口+计数】元音辅音字符串计数 II
     */
    private static boolean[] IS_VOWEL = new boolean['u' + 1];
    static {
        IS_VOWEL['a'] = IS_VOWEL['e'] = IS_VOWEL['i'] = IS_VOWEL['o'] = IS_VOWEL['u'] = true;
    }
    private long countAtLeastK(int n, char[] word, int k) {
        int[] vowelCnt = new int['u' + 1];
        int vowels = 0;
        int consonantCnt = 0;
        long count = 0L;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            //滑动窗口延伸右边
            while (j < n && (consonantCnt < k || vowels < 5)) {
                char c = word[j];
                if (IS_VOWEL[c]) {
                    if (++vowelCnt[c] == 1) ++vowels;
                } else {
                    consonantCnt++;
                }
                ++j;
            }
            if (consonantCnt < k || vowels < 5) break; //不存在满足条件的子字符串
            //找到满足至少k个辅音字符+每种元音字符至少1个的最小区间[i,j)，其中j不包含在区间内，那么后面直到结尾有多少个字符就有多少个符合条件的子字符串
            count += n - j + 1;
            //左边缩一个字符
            char c = word[i];
            if (IS_VOWEL[c]) {
                if (--vowelCnt[c] <= 0) vowels--;
            } else {
                consonantCnt--;
            }
        }
        return count;
    }
    public long countOfSubstrings(String word, int k) {
        int n = word.length();
        char[] wordChars = word.toCharArray();
        return countAtLeastK(n, wordChars, k) - countAtLeastK(n, wordChars, k + 1);
    }

    public static void main(String[] args) {
        SlideWindowSolution solution = new SlideWindowSolution();
        Assert.isTrue(4 == solution.countCompleteSubarrays(new int[]{1,3,1,2,2}));
//        Assert.isTrue(10 == solution.validSubstringCount("abcabc", "abc"));
//        Assert.isTrue(1 == solution.validSubstringCount("bcca", "abc"));

//        Assert.isTrue(4 == solution.balancedString("QWERQQQWERWEQQQQ"));
//        Assert.isTrue(2 == solution.balancedString("WERWERWE"));
//        Assert.isTrue(2 == solution.balancedString("QQQW"));
//        Assert.isTrue(3 == solution.minimumRecolors("WBBWWBBWBW", 7));
//        Assert.isTrue(0 == solution.minimumRecolors("WBWBBBW", 2));
    }
}
